from tools_algorithm import *


class Solution:
    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:
        def f(num):
            id = -1
            tot = 0
            sexp = 0
            while num >= 1 << (id + 1):
                id += 1
                per = 1 << (id + 1)  # 一组per个
                size = 1 << id  # 每组size个1，size个0
                # num前一共num + 1个数，因为0的存在。1的数量cur个
                cur = (num + 1) // per * size + max((num + 1) % per - size, 0)
                sexp += cur * id  # 幂贡献增加了这么多
                tot += cur  # 1增加了这么多
            # num前总共tot个1，幂贡献sexp
            return tot, sexp

        def sub(num: int, subHigh):
            ans = 0
            while num > 0:
                lb = num & -num  # 最低位的1
                if num.bit_count() <= subHigh:  # 从这开始减去幂贡献
                    ans += lb.bit_length() - 1  # 幂贡献就是lb长度 - 1
                num -= lb  # 叉出去，下一个
            return ans

        def sumAll(q):
            # 这么写，为了sexp还得f一遍，两个可以写一起，代码长出一个二分
            i = bisect_left(range(10**15), q, key=lambda a: f(a)[0])
            tot, sexp = f(i)
            return sexp - sub(i, tot - q)

        ans = []
        for l, r, m in queries:
            # index是r需要r+1个1，l需要l+1个1，因为作为前缀和求差，需要l前面那个位置，就是l本身
            ans.append(pow(2, sumAll(r + 1) - sumAll(l), m))
        return ans


class Solution:
    def findProductsOfElements(self, queries: List[List[int]]) -> List[int]:
        # num以下一共有tot个1，幂贡献sexp
        def f(num):
            id = -1
            tot = 0
            sexp = 0
            while num >= 1 << (id + 1):
                id += 1
                per = 1 << (id + 1)
                size = 1 << id
                cur = (num + 1) // per * size + max((num + 1) % per - size, 0)
                sexp += cur * id
                tot += cur
            return tot, sexp

        # num，高位减掉subHigh个数，一共减掉ans个幂贡献
        def sub(num: int, subHigh):
            ans = 0
            while num > 0:
                lb = num & -num
                if num.bit_count() <= subHigh:
                    ans += lb.bit_length() - 1
                num -= lb
            return ans

        def sumAll(q):
            # i = bisect_left(range(10**15), q, key=lambda a: f(a)[0])
            l, r = 0, 10**15
            tot, sexp, num = 0, 0, 0
            while l + 1 < r:
                m = ((r - l) >> 1) + l
                t, s = f(m)
                if t < q:
                    l = m
                else:
                    tot, sexp, num = t, s, m
                    r = m
            # q个1，对应数字产生sexp个贡献，多出来的tot - q个从num里减去
            return sexp - sub(num, tot - q)

        ans = []
        for l, r, m in queries:
            # 索引r共r+1个1，索引l共l+1个1，做差需要找左边界前一个也就是l
            ans.append(pow(2, sumAll(r + 1) - sumAll(l), m))
        return ans


s = Solution()
print(s.findProductsOfElements([[2, 1000000000000000, 3]]))
# print(s.findProductsOfElements([[1, 3, 7]]))
# print(s.findProductsOfElements([[2, 5, 3], [7, 7, 4]]))
# print(s.findProductsOfElements([[7, 7, 4]]))
